<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/2002/REC-xhtml1-20020801/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <meta http-equiv="Content-Type"
        content="text/html; charset=ISO-8859-1" />
  <title>Code Examples for Programming in Scala, Third Edition</title>
  <link rel="stylesheet" href="style.css" type="text/css"/>
</head>
<body>

<div id="mainTitles"><h3>Code Examples for</h3><h2>Programming in Scala, Third Edition</h2></div>  <p><a href="../index.html">
    Return to chapter index
  </a></p>
  <h2>25 The Architecture of Scala Collections</h2>

    <li>25.1 <a href="#sec1">Builders</a></li>
    <li>25.2 <a href="#sec2">Factoring out common operations</a></li>
    <li>25.3 <a href="#sec3">Integrating new collections</a></li>
    <li>25.4 <a href="#sec4">Conclusion</a></li>
  </ul>

  <h3><a name="sec1"></a>25.1 Builders</h3>

  <pre><hr>
  package scala.collection.generic

  class Builder[-Elem, +To] {
    def +=(elem: Elem): this.type
    def result(): To
    def clear()
    def mapResult[NewTo](f: To =&gt; NewTo): Builder[Elem, NewTo]
      = ...
  }

<hr>
  scala&gt; val buf = new ArrayBuffer[Int]
<span class="output">  buf: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()</span>

  scala&gt; val bldr = buf mapResult (_.toArray)
<span class="output">  bldr: scala.collection.mutable.Builder[Int,Array[Int]]</span>
<span class="output">    = ArrayBuffer()</span>

<hr>
  </pre>
  <h3><a name="sec2"></a>25.2 Factoring out common operations</h3>

  <pre><hr>
  trait TraversableLike[+Elem, +Repr] { ... }

<hr>
  package scala.collection

  trait TraversableLike[+Elem, +Repr] {
    def newBuilder: Builder[Elem, Repr] // deferred
    def foreach[U](f: Elem =&gt; U)        // deferred
            ...
    def filter(p: Elem =&gt; Boolean): Repr = {
      val b = newBuilder
      foreach { elem =&gt; if (p(elem)) b += elem }
      b.result
    } 
  }

<hr>
  scala&gt; import collection.immutable.BitSet
<span class="output">  import collection.immutable.BitSet</span>

  scala&gt; val bits = BitSet(1, 2, 3)
<span class="output">  bits: scala.collection.immutable.BitSet = BitSet(1, 2, 3)</span>

  scala&gt; bits map (_ * 2)
<span class="output">  res13: scala.collection.immutable.BitSet = BitSet(2, 4, 6)</span>

  scala&gt; bits map (_.toFloat)
<span class="output">  res14: scala.collection.immutable.Set[Float] =</span>
<span class="output">    Set(1.0, 2.0, 3.0)</span>

<hr>
    scala&gt; Map("a" -&gt; 1, "b" -&gt; 2) map { case (x, y) =&gt; (y, x) }
<span class="output">    res3: scala.collection.immutable.Map[Int,java.lang.String] = </span>
<span class="output">      Map(1 -&gt; a, 2 -&gt; b)</span>

    scala&gt; Map("a" -&gt; 1, "b" -&gt; 2) map { case (x, y) =&gt; y }
<span class="output">    res4: scala.collection.immutable.Iterable[Int] = </span>
<span class="output">      List(1, 2)</span>

<hr>
  def map[B, That](f: Elem =&gt; B)
      (implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(this)
    for (x &lt;- this) b += f(x)
    b.result
  }

<hr>
  package scala.collection.generic

  trait CanBuildFrom[-From, -Elem, +To] {
    // Creates a new builder 
    def apply(from: From): Builder[Elem, To] 
  }

<hr>
  CanBuildFrom[Set[_], A, Set[A]]

<hr>
  scala&gt; val xs: Iterable[Int] = List(1, 2, 3)
<span class="output">  xs: Iterable[Int] = List(1, 2, 3)</span>

  scala&gt; val ys = xs map (x =&gt; x * x)
<span class="output">  ys: Iterable[Int] = List(1, 4, 9)</span>

<hr>
  </pre>
  <h3><a name="sec3"></a>25.3 Integrating new collections</h3>

  <pre><hr>
  abstract class Base
  case object A extends Base
  case object T extends Base
  case object G extends Base
  case object U extends Base

  object Base {
    val fromInt: Int =&gt; Base = Array(A, T, G, U)
    val toInt: Base =&gt; Int = Map(A -&gt; 0, T -&gt; 1, G -&gt; 2, U -&gt; 3)
  }

<hr>
import collection.IndexedSeqLike
import collection.mutable.{Builder, ArrayBuffer}
import collection.generic.CanBuildFrom

final class RNA1 private (val groups: Array[Int],
    val length: Int) extends IndexedSeq[Base] {

  import RNA1._

  def apply(idx: Int): Base = {
    if (idx &lt; 0 || length &lt;= idx)
      throw new IndexOutOfBoundsException
    Base.fromInt(groups(idx / N) &gt;&gt; (idx % N * S) &amp; M)
  }
}

object RNA1 {

  // Number of bits necessary to represent group
  private val S = 2            

  // Number of groups that fit in an Int
  private val N = 32 / S       

  // Bitmask to isolate a group
  private val M = (1 &lt;&lt; S) - 1 

  def fromSeq(buf: Seq[Base]): RNA1 = {
    val groups = new Array[Int]((buf.length + N - 1) / N)
    for (i &lt;- 0 until buf.length)
      groups(i / N) |= Base.toInt(buf(i)) &lt;&lt; (i % N * S)
    new RNA1(groups, buf.length)
  }

  def apply(bases: Base*) = fromSeq(bases)
}

<hr>
  scala&gt; val xs = List(A, G, T, A)
<span class="output">  xs: List[Product with Base] = List(A, G, T, A)</span>

  scala&gt; RNA1.fromSeq(xs)
<span class="output">  res1: RNA1 = RNA1(A, G, T, A)</span>

  scala&gt; val rna1 = RNA1(A, U, G, G, T)
<span class="output">  rna1: RNA1 = RNA1(A, U, G, G, T)</span>

<hr>
  scala&gt; rna1.length
<span class="output">  res2: Int = 5</span>
  
  scala&gt; rna1.last
<span class="output">  res3: Base = T</span>

  scala&gt; rna1.take(3)
<span class="output">  res4: IndexedSeq[Base] = Vector(A, U, G)</span>

<hr>
  def take(count: Int): RNA1 = RNA1.fromSeq(super.take(count))

<hr>
final class RNA2 private (
  val groups: Array[Int],
  val length: Int
) extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA2] {

  import RNA2._
    
  override def newBuilder: Builder[Base, RNA2] = 
    new ArrayBuffer[Base] mapResult fromSeq

  def apply(idx: Int): Base = // as before
}

<hr>
<em>\mbox{RNA2.scala:5: error: overriding method newBuilder in trait}</em>
<em>\mbox{TraversableLike of type =&gt; scala.collection.mutable.Builder[Base,RNA2];}</em>
<em>\mbox{ method newBuilder in trait GenericTraversableTemplate of type}</em>
<em>\mbox{ =&gt; scala.collection.mutable.Builder[Base,IndexedSeq[Base]] has}</em>
<em>\mbox{ incompatible type}</em>
<em>\mbox{class RNA2 private (val groups: Array[Int], val length: Int) }</em>
      ^
<em>\mbox{one error found}</em>

<hr>
  scala&gt; val rna2 = RNA2(A, U, G, G, T)
<span class="output">  rna2: RNA2 = RNA2(A, U, G, G, T)</span>

  scala&gt; rna2 take 3
<span class="output">  res5: RNA2 = RNA2(A, U, G)</span>

  scala&gt; rna2 filter (U !=)
<span class="output">  res6: RNA2 = RNA2(A, G, G, T)</span>

<hr>
  scala&gt; val rna = RNA(A, U, G, G, T)
<span class="output">  rna: RNA = RNA(A, U, G, G, T)</span>

  scala&gt; rna map { case A =&gt; T case b =&gt; b }
<span class="output">  res7: RNA = RNA(T, U, G, G, T)</span>

<hr>
  scala&gt; rna ++ rna
<span class="output">  res8: RNA = RNA(A, U, G, G, T, A, U, G, G, T)</span>

<hr>
  scala&gt; rna map Base.toInt
<span class="output">  res2: IndexedSeq[Int] = Vector(0, 3, 2, 2, 1)</span>

  scala&gt; rna ++ List("missing", "data")
<span class="output">  res3: IndexedSeq[java.lang.Object] = </span>
<span class="output">    Vector(A, U, G, G, T, missing, data)</span>

<hr>
  scala&gt; val rna2 = RNA2(A, U, G, G, T)
<span class="output">  rna2: RNA2 = RNA2(A, U, G, G, T)</span>

  scala&gt; rna2 map { case A =&gt; T case b =&gt; b }
<span class="output">  res0: IndexedSeq[Base] = Vector(T, U, G, G, T)</span>

  scala&gt; rna2 ++ rna2
<span class="output">  res1: IndexedSeq[Base] = Vector(A, U, G, G, T, A, U, G, G, T)</span>

<hr>
  def map[B, That](f: Elem =&gt; B)
    (implicit cbf: CanBuildFrom[Repr, B, That]): That

<hr>
final class RNA private (val groups: Array[Int], val length: Int) 
  extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA] {

  import RNA._

  // Mandatory re-implementation of `newBuilder` in `IndexedSeq`
  override protected[this] def newBuilder: Builder[Base, RNA] = 
    RNA.newBuilder

  // Mandatory implementation of `apply` in `IndexedSeq`
  def apply(idx: Int): Base = {
    if (idx &lt; 0 || length &lt;= idx)
      throw new IndexOutOfBoundsException
    Base.fromInt(groups(idx / N) &gt;&gt; (idx % N * S) &amp; M)
  }

  // Optional re-implementation of foreach, 
  // to make it more efficient.
  override def foreach[U](f: Base =&gt; U): Unit = {
    var i = 0
    var b = 0
    while (i &lt; length) {
      b = if (i % N == 0) groups(i / N) else b &gt;&gt;&gt; S
      f(Base.fromInt(b &amp; M))
      i += 1
    }
  }
}

<hr>
object RNA {

  private val S = 2            // number of bits in group
  private val M = (1 &lt;&lt; S) - 1 // bitmask to isolate a group
  private val N = 32 / S       // number of groups in an Int

  def fromSeq(buf: Seq[Base]): RNA = {
    val groups = new Array[Int]((buf.length + N - 1) / N)
    for (i &lt;- 0 until buf.length)
      groups(i / N) |= Base.toInt(buf(i)) &lt;&lt; (i % N * S)
    new RNA(groups, buf.length)
  }

  def apply(bases: Base*) = fromSeq(bases)

  def newBuilder: Builder[Base, RNA] = 
    new ArrayBuffer mapResult fromSeq

  implicit def canBuildFrom: CanBuildFrom[RNA, Base, RNA] = 
    new CanBuildFrom[RNA, Base, RNA] {
      def apply(): Builder[Base, RNA] = newBuilder
      def apply(from: RNA): Builder[Base, RNA] = newBuilder
    }
}

<hr>
import collection._

class PrefixMap[T]
extends mutable.Map[String, T] 
   with mutable.MapLike[String, T, PrefixMap[T]] {

  var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty
  var value: Option[T] = None

  def get(s: String): Option[T] =
    if (s.isEmpty) value
    else suffixes get (s(0)) flatMap (_.get(s substring 1))

  def withPrefix(s: String): PrefixMap[T] = 
    if (s.isEmpty) this
    else {
      val leading = s(0)
      suffixes get leading match {
        case None =&gt;
          suffixes = suffixes + (leading -&gt; empty)
        case _ =&gt;
      }
      suffixes(leading) withPrefix (s substring 1)
    }

  override def update(s: String, elem: T) =
    withPrefix(s).value = Some(elem)

  override def remove(s: String): Option[T] =
    if (s.isEmpty) { val prev = value; value = None; prev }
    else suffixes get (s(0)) flatMap (_.remove(s substring 1))

  def iterator: Iterator[(String, T)] =
    (for (v &lt;- value.iterator) yield ("", v)) ++
    (for ((chr, m) &lt;- suffixes.iterator; 
          (s, v) &lt;- m.iterator) yield (chr +: s, v))
    
  def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this }

  def -= (s: String): this.type  = { remove(s); this }

  override def empty = new PrefixMap[T]
}

<hr>
  scala&gt; val m = PrefixMap("abc" -&gt; 0, "abd" -&gt; 1, "al" -&gt; 2, 
    "all" -&gt; 3, "xy" -&gt; 4)
<span class="output">  m: PrefixMap[Int] = Map((abc,0), (abd,1), (al,2), (all,3),</span>
<span class="output">    (xy,4))</span>

<hr>
  scala&gt; m withPrefix "a"
<span class="output">  res14: PrefixMap[Int] = Map((bc,0), (bd,1), (l,2), (ll,3))</span>

<hr>
import scala.collection.mutable.{Builder, MapBuilder}
import scala.collection.generic.CanBuildFrom

object PrefixMap {
  def empty[T] = new PrefixMap[T]

  def apply[T](kvs: (String, T)*): PrefixMap[T] = {
    val m: PrefixMap[T] = empty
    for (kv &lt;- kvs) m += kv
    m
  }

  def newBuilder[T]: Builder[(String, T), PrefixMap[T]] = 
    new MapBuilder[String, T, PrefixMap[T]](empty)

  implicit def canBuildFrom[T]
    : CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] = 
      new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {
        def apply(from: PrefixMap[_]) = newBuilder[T]
        def apply() = newBuilder[T]
      }
}

<hr>
  scala&gt; PrefixMap("hello" -&gt; 5, "hi" -&gt; 2)
<span class="output">  res0: PrefixMap[Int] = Map((hello,5), (hi,2))</span>

  scala&gt; PrefixMap.empty[String]
<span class="output">  res2: PrefixMap[String] = Map()</span>

<hr>
  scala&gt; res0 map { case (k, v) =&gt; (k + "!", "x" * v) }
<span class="output">  res8: PrefixMap[String] = Map((hello!,xxxxx), (hi!,xx))</span>

<hr>
  </pre>
  <h3><a name="sec4"></a>25.4 Conclusion</h3>


 <table>
 <tr valign="top">
 <td>
 <div id="moreinfo">
 <p>
 For more information about <em>Programming in Scala, Third Edition</em> (the "Stairway Book"), please visit:
 </p>
 
 <p>
 <a href="http://www.artima.com/shop/programming_in_scala_3ed">http://www.artima.com/shop/programming_in_scala_3ed</a>
 </p>
 
 <p>
 and:
 </p>
 
 <p>
 <a href="http://booksites.artima.com/programming_in_scala_3ed">http://booksites.artima.com/programming_in_scala_3ed</a>
 </p>
 </div>
 </td>
 <td>
 <div id="license">
 <p>
   Copyright &copy; 2007-2016 Artima, Inc. All rights reserved.
 </p>

 <p>
   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at
 </p>

 <p style="margin-left: 20px">
   <a href="http://www.apache.org/licenses/LICENSE-2.0">
     http://www.apache.org/licenses/LICENSE-2.0
   </a>
 </p>

 <p>
   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
   implied.
   See the License for the specific language governing permissions and
   limitations under the License.
 </p>
 </div>
 </td>
 </tr>
 </table>

</body>
</html>
